package com.shopee;

/**
 * 统计一个数（二进制）中有多少个 1
 */
public class FindLength1ofTheNumbers {

    public static void main(String[] args) {

        int num = 12 ;
        int count = 0 ;

        /**
         * redis BitMaps : bitcount
         * 时间复杂度 数字中有多少个  就执行多少次
         * 解题思路
         *  因为 num-1 总会从num的最右边一个 1 上借位， 12： 1100  ， 11： 1011
         *  这样 n & (n-1) 后，会将n最右边的 1 变为 0 ，此时count++， 当n == 0 时，则代表 已经将n中的1全部变为0
         */
        while (num != 0 ){
            num &= (num - 1) ;
            count ++ ;
        }


        /**
         * 时间复杂度 ： 因为每次右移相当于 除2 ，所以时间复杂度为 lg(n)
         * 依次判断 num 的最右边一位是否为 0 ， 是的话count 加 1
         * 然后 num 右移一位
         */
        while (num != 0 ){
            if ( (num & 1) == 1 ){
                //最后一位为 1
                count ++ ;
            }
            num >>= 1 ;
        }

        System.out.println(count);

    }

}
